The subject invention relates to cryptosystems. More particularly it relates to a method and system for solving the word problem in braid group cryptosystems.
A group is a three-tuple (G, •, e) where G is a non-empty set; • is a binary operation such that if a and b are elements of G then a•b is an element of G; and e is an identity element such that:                For all a,b,c in G: a•(b•c)=(a•b)•c        For all a in G: a•e=a=e•a        For all a in G there exists a−1 in G such that: a•a−1=e=a−1•a        
A particular type of group that has been found to be useful as a basis for cryptographic systems is an n-braid group as will be described below.
FIG. 1 illustrates the elementary braid σi, the inverse elementary braid σi−1 and the “product” σi•σi+1. Elementary braids are most conveniently considered as operations on strands that connect pairs of upper and lower points i (i=1,2, . . . , n). As seen in FIG. 1, σi is the operation of crossing strand s(i+1) (the strand connected to upper point i+1) over strand s(i) so that strand s(i+1) connects upper point i+1 to lower point i and σi−1 crosses strand s(i) over strand s(i+1).
FIG. 1 also illustrates a binary operation (hereinafter sometimes “multiplication”) represented by •. We multiply two elementary braids σi, σj (either or both of which can be inverse elementary braids) by first performing the operation σi, and then the operation σj; as is shown for σi•σi+1 in FIG. 1. It should be noted that, as shown in FIG. 1, σi•σi+1≠σi+1•σi.
The elementary braids and inverses are used to define an n-braid group. An n-braid is defined as the braid generated on n strands by any product of m elementary braids, m>0, chosen from the set {σ1, σ2, . . . σn, σ1−1, σ2−1, . . . σn−1}. It is immediately apparent from FIG. 1 that the definition of multiplication can be extended to the multiplication of two braids α, β by defining α•β to mean performing all of the elementary operations in α. followed by all of the elementary operations in β. (Hereinafter, for simplicity, the symbol “•” may not be explicitly written; e.g. αβ=α•β. The set of all n-braids is defined as Bn. The n-braid group is then: (Bn, •, e), where e is the braid that contains no crosses.
FIG. 2 shows the braid σi•σi−1. It is apparent from inspection of FIG. 2 that σi•σi−1=e=σi−1•σi. (Visualize “pulling the stands tight” so that they lie parallel.) From this it immediately follows that:
                                                        ∏                              i                =                0                                            m                -                1                                      ⁢                                                  ⁢                                          σ                                  a                  ⁡                                      (                    i                    )                                                                    b                  ⁡                                      (                    i                    )                                                              ·                                                ∏                                      i                    =                                          m                      -                      1                                                        0                                ⁢                                                                  ⁢                                  σ                                      a                    ⁡                                          (                      i                      )                                                                            -                                          b                      ⁡                                              (                        i                        )                                                                                                                          =          ⅇ                ;                            (        1        )                            where a(i) is in {0,1,2, . . . n} and b(i) is in {−1,1}. That is, for each braid α in Bn, α−1 can be formed by taking the product of the inverses of each elementary braid in α in the reverse order.        
It has been shown that the n-braid group Bn (i.e. the group comprising the set of braids Bn) is defined by braid group binary operation rules:Bn=σ1, . . . σn|σiσjσi=σjσiσj; |i−j|=1: σiσj=σjσi; |i−j|>1;  (2)as is illustrated in FIG. 3.
From (1) and (2) above the above it will be apparent to those skilled in the art each braid in Bn can be expressed by a plurality of words of the form:
            ∏              i        =        0                    m        -        1              ⁢                  ⁢          σ              a        ⁡                  (          i          )                            b        ⁡                  (          i          )                      ;indeed, since m can increase without limit, by an infinity of words. (As used herein the term “word” refers to expressions of the form:
            ∏              i        =        0                    m        -        1              ⁢                  ⁢          σ              a        ⁡                  (          i          )                            b        ⁡                  (          i          )                      ;while the terms “n-braid” and “braid” refer to the structure created on n strands by the operations specified by a word. Words are termed equal if they express the same braid.)
It is clear from observation that every braid induces a permutation Π=(a1, . . . an) on 1,2, n such that the ith upper point is connected to the aith lower point by strand s (i). It can be shown that every permutation Π can be written as a particular positive braid having no two strings cross each other more than once, which is commonly referred to as a permutation braid. (By “positive braid” herein is meant a braid wherein the left going strand always crosses over the right going strand; i.e. a braid which can be expressed as a word which does not include any inverse elementary braids: σi−1. When reference is made herein to a word expressing a “permutation braid” such word should be understood to be in a standard form known to those skilled in the art.)
An important permutation braid in Bn is the “fundamental braid” which induces the permutation (n, n−1, . . . 1) and can be expressed as a word in the standard form:(σn−1 . . . σ1)(σn−1 . . . σ2) . . . (σn−1 . . . σn−2)σn−1≡Δ.It has been shown that every braid in Bn can be expressed as:
                    ∏                  j          =          1                r            ⁢                          ⁢                        Δ          j                      b            ⁡                          (              j              )                                      ·        P              ≡                  Δ        k            ·      P        ;where b(j) is selected from {1,−1}, and P is a positive braid. It is also known that a positive braid P can be expressed as a product of permutation braids, A0 . . . Ap−1. 
As is generally the case for modern cryptosystems, braid group cryptosystems are based on a hard problem. (Those skilled in the art will recognize that a hard problem is a problem for which the time required to find a solution increases with some parameter so rapidly that it is not feasible to find a solution for large enough values of the parameter without use of some secret information, or “key”. For braid group cryptosystems the parameter is typically m, the word length or number of elementary braids in a word. Such problems are said to require “greater than polynomial time” or “greater than NP time”.)
A hard problem in braid groups is the conjugacy search problem, which can be stated as: given x and b=axa−1, a, b, and x all elements of Bn, find a. (Of course, if x is expressed as a particular word, w(x), b can not simply be expressed as the concatenation w(a)_w(x)_w(a−1) but must be transformed in some manner so that w(a) (and thus a) cannot be identified by simple pattern matching of w(x).)
FIG. 4 shows the known Diffie-Hillman Key Exchange Mechanism, which uses the conjugacy search problem to allow parties to exchange cryptographic keys over a non-secure communications link.
At step 10 parties A and B partition the n-braid set Bn into subsets LBn and RBn such that: for all a in LBn and all b in RBn, a•b=b•a. Preferably this accomplished by choosing LBn to be the subset of braids involving only twists of the leftmost strands 0,1, . . I, and RBn to be the subset of braids involving only twists of the rightmost strands n−r, . . . n; where I+r=n. The result follows immediately from (2).
At step 12 the parties agree upon braid x in Bn. Braid x is chosen to be reasonably complex so as to protect against brute force attacks. Those skilled in the art will recognize how to select x to provide a desired level of security. Note that steps 10 and 12 can be carried out over a non-secure link such as a broadcast channel or even by publication.
At step 14A party A generates and maintains in secrecy a braid a in LBn. At step 16A party A computes and sends to party B a braid α=axa−1. At step 20A party A receives a braid β=bxb−1 from party B; b in RBn and similarly maintained in secrecy. At step 22A party A computes a braid K=a βa−1=abxa−1b−1.
Party B carries out complementary steps 14B through 22B for b in RBn to obtain K=bαb−1=baxa−1b−1.
Because of the way in which LBn and RBn are selected A and B can be sure that the values each obtains for braid K are equal, i.e. represent the same braid structure; and, because to do so would require solving the hard conjugacy search problem, an adversary cannot determine (in a reasonable time, or at a reasonable cost) a or b from knowledge of x and α and β; and thus cannot determine K.
In general A and B obtain words expressing K, w (K), w′ (K), which are not the same. Accordingly, at steps 24A and 24B A and B each derives an identical key, which is typically a key for a symmetric key encryption system, from the expressions w (K) and w′ (K), respectively; as will described further below.
A basic problem, upon which the success of braid group cryptosystems in general depends is the word problem, which can be stated as: given two distinct words w (y), expressing a braid y in Bn, and w(δ), expressing a braid δ in Bn, is y=δ? Equivalently, does an algorithm, C, exist which will transform any word w(y) into a standard form, C(w(y)), such that: C(w(y)) is the same as C(w′(δ)) if and only if y=δ? Accordingly at steps 24A and 24B parties A and B compute C(w(K)) and C(w′(K)) to obtain identical expressions for K and recover the information content of braid K. (By “recover” herein is meant to express in a convenient standard form.) Then any convenient, agreed upon function can be used to generate a secret, common key.
While the word problem is not considered hard in the cryptographic sense and methods for solving it do exist, it is believed that a need for simpler, faster methods continues
While the word problem has been described with respect to a particular key exchange mechanism, those skilled in the art will recognize that the word problem and systems and methods for its solution have general applicability to braid group cryptographic systems.
Other methods for performing operations on a different representation of braid groups (the “band-generator” representation) have been presented at the AsiaCrypt 2001. Conference by Cha et al. While these methods may provide analogous results in the band-generator braid group representation they are structurally and logically distinct from, and neither teach nor suggest, the methods of the present invention as described and claimed herein.
Thus it is an object of the subject invention to provide a system and method for solving the word problem in braid group cryptosystems.